Renji Set Query
の複合。
…というわけで、ここからはRange Set Queryの概要・解き方について解説していく。
問題概要
$ N枚のシールが横一列に並んでいて、左から$ i番目のシールは種類$ c_iである。
$ Q個の整数のペア$ (L_1,R_1),(L_2,R_2),...,(L_Q,R_Q)が与えられる。以下の$ Q個の質問に答えよ。
左から$ L_i番目にあるシールから、$ R_i番目にあるシールまでを手に入れたとき、被りを除いて何種類獲得できるか。
例
code:sample.txt
2 5 6 4 2 1 7 2 7
制約
入力はすべて整数
$ 1 \leq N,Q \leq 5 \times 10^5
$ 1 \leq c_i \leq N
$ 1 \leq L_i \leq R_i \leq N
考察
普通にやれば、質問$ 1つあたり最大で$ N個のシールを見る必要があるので、全体で$ O(NQ)かかってしまい、爆発的な計算時間がかかってしまう。よって、なんらかの工夫をして、計算時間を削減する必要がある。
ここで、「被りを取り除いた種類数」という考え方は扱いづらいので、
なにか条件を言い換えて、その条件を満たすものを単純に数え上げる
という方針で計算回数の削減を図ってみよう。
区間内にたくさんシールがあっても、$ 1枚シールがあっても、そのシールは結局$ 1種類としかカウントされないことに着目する。
つまり、ある種類のシールについて$ 1枚あることが確認できた場合は、以降その種類のシールのことは考えなくてよい。
すると、「被りを除いた種類数」は、「$ L_i番目にあるシールから右側だけを見たとき、その種類のうち最も左にあるようなシールが何枚あるか」と言い換えることができる。
例えば、$ L_i=1, R_i=6の以下の場合においては、「$ 1番目にあるシールから右側だけを見て、その種類のうち最も左にあるようなシール」だけが意味を持つ。
https://gyazo.com/096c54562834798665bb4c169b38cff7
よって、種類数は$ 5である。
よって、例えば全ての質問で$ L_i=1だった場合は、以下のような手順でそれぞれの質問に答えることができる。
長さ$ Nの新しい数列$ Bを用意し、左から$ i番目の数値$ B_iを以下のように定義する。
シールの数列$ Cを、左から$ 1番目のシールから右を順番に見たとき、そのシールが初めて出てくる種類のシールなら$ B_i=1
そうでないなら$ B_i=0
https://gyazo.com/9718357221ea2163d5432fb60cae32f2
$ Bの値は、全体で$ O(N)で計算できる。
各質問に対して、$ A_1, A_2, ...,A_Rの合計値を計算する。
これは、累積和を用いることで全体$ O(Q)で計算できる。 よって、全体で$ O(N+Q)で解くことができる。
この解法を拡張することで、$ L_iがどんな値でも回答できるような方法を考える。
$ L_i=lに対して、対応する配列$ Bを$ B \lbrack l \rbrackと定義する。
つまり、$ B \lbrack l \rbrack _iを$ B \lbrack l \rbrackの左から$ i番目の数値と定義すると、
$ i < lのとき、$ B \lbrack l \rbrack _i = 0
$ i \geq lのとき、
シールの数列$ Cを、左から$ l番目のシールから右を順番に見たとき、そのシールが初めて出てくる種類のシールなら$ B \lbrack l \rbrack _i = 1
そうでないなら$ B \lbrack l \rbrack _i=0
とする。
このとき、$ B \lbrack 1 \rbrackから$ B \lbrack 2 \rbrackを少ない計算回数で求めることができれば、その方法を$ B \lbrack 2 \rbrackから$ B \lbrack 3 \rbrack、$ B \lbrack 3 \rbrackから$ B \lbrack 4 \rbrackという風に繰り返し用いることで、全ての$ L_iについて$ B \lbrack L_i \rbrackを計算できる。
さて、$ B \lbrack 1 \rbrackから$ B \lbrack 2 \rbrackへの変化を考えたとき、$ 1番目のシールが範囲外になるので、
$ Bの左から$ 1番目の数値は$ 1から$ 0に
もし$ 2番目のシールより左側にシール$ c_1があるなら、それらのうち最も右側にあるシールを$ j番目として、$ Bの左から$ j番目の要素は$ 0から$ 1に
変更される。
https://gyazo.com/c46983248969eb6f8bbbff72f83dd2b3
$ B \lbrack 1 \rbrackから$ B \lbrack 2 \rbrackの変更の例。
今、$ c_1=2なので、「$ 2番目のシールより左側のうち、最も右側にある同種類のシール」は、$ 5番目のものなので、$ j=5となる。
つまり、$ B \lbrack 1 \rbrackから$ B \lbrack 2 \rbrackで、最大でも$ 2つの要素しか変更されないので、$ Bを使いまわすことで、$ 2回の変更で$ Bを更新することができる。
よって、$ l=1,2,...,Nの合計$ Nパターンにおける$ B \lbrack l \rbrackは、$ lが小さい順に考えることで、全体で$ 2N回の変更で全ての$ Bについて計算することができる。
具体的には、$ B \lbrack i \rbrackから$ B \lbrack i+1 \rbrackについて、
-$ B \lbrack i+1 \rbrack _i = 0
- もし$ i+1番目のシールより左側にシール$ c_iがあるなら、そのシールを$ j番目として、
-$ B \lbrack i+1 \rbrack _j = 1
それ以外の$ jについてはそのまま、
- $ B \lbrack i+1 \rbrack _j = B \lbrack i \rbrack _j
とすれば更新できる。
$ i+1番目のシールより左側のシール$ c_iの場所は、「種類$ kのシールがある位置の数列」の列を持って、どこまで見たかを記録しておけば、前計算$ O(N)、$ 1回の更新辺り$ O(1)で求めることができる。
これで、すべての$ Lについて$ B \lbrack L \rbrackを計算することができたので、あとは、
数列の$ 1箇所の値を変更する
数列のある区間の合計を計算する
を少ない計算回数で実行できれば、この問題を解くことができる。
よって、この問題を全体$ O(N \, log \, N)で解くことができた。
実装例（C++）
また、「種類$ kのシールがある位置の数列」の列は、それぞれ逆順にして最後尾を常に見ることで、「どこまで見たか」の情報を明示的に持たずに済むようにしている。
code:answer.cpp
using namespace std;
using namespace atcoder;
int main() {
int N, Q;
cin >> N >> Q;
vector<int> C(N);
for (int i = 0; i < N; i++) {
}
vector<int> ans(Q);
vector<vector<pair<int, int>>> queries(N);
// querieslは、[l, r)に対する質問のうち、l=Lであるものの{R,queryが何番目かを表す数字}のペアの配列 for (int queryId = 0; queryId < Q; queryId++) {
int L, R;
cin >> L >> R;
L--; R--;
R++;
queriesL.emplace_back(R, queryId); }
fenwick_tree<int> B(N);
vector<vector<int>> ids(N);
for (int i = 0; i < N; i++) {
B.add(i, 1);
}
}
for (int i = 0; i < N; i++) {
reverse(idsi.begin(), idsi.end()); }
for (int L = 0; L < N; L++) {
// Lを固定して、[L, R)に対する質問を処理
}
B.add(ids[CL].back(), -1); B.add(ids[CL].back(), 1); }
}
// i番目の質問の答えを出力
for (int i = 0; i < Q; i++) {
}
}